package net.lainiao.leetcode;

import net.lainiao.leetcode.base.TreeNode;

import java.util.*;

public class LintCode71 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left=new TreeNode(15);
        root.right.right=new TreeNode(7);
        LintCode71 code71=new LintCode71();
        Object object=code71.zigzagLevelOrder(root);
        System.out.println(object);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        HashMap<Integer,List<Integer>> map=new HashMap<>();
        eachTreeNode(root,map,0);
        List<List<Integer>> result=new ArrayList<>();
        for(Map.Entry<Integer,List<Integer>> entry: map.entrySet()){
            if(entry.getKey()%2!=0){
                Collections.reverse(entry.getValue());
            }
            result.add(entry.getValue());
        }
        return result;
    }

    private void eachTreeNode(TreeNode node, HashMap<Integer, List<Integer>> map, int depth) {
        if(node==null){
            return;
        }
        if(!map.containsKey(depth)){
            map.put(depth,new ArrayList<>());
        }
        map.get(depth).add(node.val);
        eachTreeNode(node.left,map,depth+1);
        eachTreeNode(node.right,map,depth+1);
    }
}
